package LeetCode.interview;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

import LeetCode.interview._101_Symmetric_Tree.TreeNode;

import util.LogUtils;

/*
 * 
原题

　　Given a binary tree, determine if it is height-balanced. 
　　For this problem, a height-balanced binary tree is defined as a binary tree in which 
	the depth of the two subtrees of every node never differ by more than 1. 

题目大意

　　给定一棵平衡二叉树，判断它是否是高度平衡的。一棵高度平衡的二叉树是左右子树的高度相差不超过1，对其左右子树也是如此。 
	注：高度平衡是指：左右子树深度差(绝对值)<=1

解题思路
	递归分治法求解。 


 * @Date 2017-09-13 23：31
 */
public class _110_Balanced_Binary_Tree {
	
	public class TreeNode {
	    int val;
	    TreeNode left;
	    TreeNode right;
	    TreeNode(int x) { val = x; }
	    public TreeNode(int x, TreeNode l, TreeNode r) {val = x; left = l; right = r;}
	}

	/**
	 * 
	 * @param nums
	 * @return
	 */
	public boolean isBalanced(TreeNode node) {
		if (node == null)					return true;	//叶子节点肯定是棵平衡树
		int lDepth = calDepth(node.left);
		int rDepth = calDepth(node.right);
		if (Math.abs(lDepth - rDepth) > 1)	return false;
		return isBalanced(node.left) && isBalanced(node.right);
	}
	
	/**
	 * 计算深度
	 * @param node
	 * @return
	 */
	private int calDepth(TreeNode node) {
		if (node == null) 			//空节点深度0
			return 0;
		if (node.left==null && node.right==null) 
			return 1;
		else //eg:某节点左子树的深度为0，右子树的深度为2, 则当前节点深度为3
			return Math.max(calDepth(node.left), calDepth(node.right))+1;	
	}

	
	private TreeNode newTree2() {
		return new TreeNode(1, 
					new TreeNode(2, 
							new TreeNode(4, 
									new TreeNode(6), new TreeNode(7,
															null, new TreeNode(8))
							), new TreeNode(5)
					), 
					new TreeNode(3, 
							null, 	null)
				);
	}
	
	
	//中序遍历：看下结果
    public void traverse (TreeNode rs) {
    	if (rs == null)	return;
    	traverse(rs.left);
    	LogUtils.print(rs.val);
    	traverse(rs.right);
    }
	
	
	public static void main(String[] args) {
		_110_Balanced_Binary_Tree obj = new _110_Balanced_Binary_Tree();
		LogUtils.println("结果", 
				obj.isBalanced(
						obj.newTree2()	
				));
	}
}
